package leetcode_1000;

import java.util.Arrays;

public class ValidPermutationsForDISequence_903_ {
	public static void main(String[] args) {
		ValidPermutationsForDISequence_903_ test=new ValidPermutationsForDISequence_903_();
		System.out.println(test.numPermsDISequence("DI"));
	}
	
	public int numPermsDISequence(String S) {
		final int MOD=1_000_000_007;
		char[] chars=S.toCharArray();
		//dp的意义是 以i位j结尾的合法解个数
		int [][]dp=new int[chars.length+1][chars.length+1];
		Arrays.fill(dp[0], 1);//第0位全赋1 因为全部合法
		//因为这样的遍历方式 决定了当i位是j的时候 前面不可能出现高于I的情况
		//这样也避免了 202这种情况的出现
		for(int i=1;i<=chars.length;++i) {
			for(int j=0;j<=i;++j) {//此处要注意 j必须小于等于i 
				if(chars[i-1]=='D') {//此处是降 所以上一位要高与j
					for(int k=j;k<i;++k) {//k从j开始计算
						dp[i][j]+=dp[i-1][k];
						dp[i][j]%=MOD;
					}
				}
				else {
					for(int k=0;k<j;++k) {
						dp[i][j]+=dp[i-1][k];
						dp[i][j]%=MOD;
					}
				}
			}
		}
		int res=0;
		for(int x:dp[chars.length])
			res=(res+x)%MOD;
		return res;
	}
}
